//You are given an array of k linked-lists lists, each linked-list is sorted in 
//ascending order. 
//
// Merge all the linked-lists into one sorted linked-list and return it. 
//
// 
// Example 1: 
//
// 
//Input: lists = [[1,4,5],[1,3,4],[2,6]]
//Output: [1,1,2,3,4,4,5,6]
//Explanation: The linked-lists are:
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//merging them into one sorted list:
//1->1->2->3->4->4->5->6
// 
//
// Example 2: 
//
// 
//Input: lists = []
//Output: []
// 
//
// Example 3: 
//
// 
//Input: lists = [[]]
//Output: []
// 
//
// 
// Constraints: 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] is sorted in ascending order. 
// The sum of lists[i].length won't exceed 10^4. 
// 
// Related Topics 堆 链表 分治算法 
// 👍 1292 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.util.PriorityQueue;

//Java：Merge k Sorted Lists
class P23MergeKSortedLists {
    public static void main(String[] args) {
        Solution solution = new P23MergeKSortedLists().new Solution();
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(4);
        node1.next.next = new ListNode(5);
        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);
        ListNode node3 = new ListNode(2);
        node2.next = new ListNode(6);
        solution.mergeKLists(new ListNode[]{node1, node2, node3});
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            if (lists.length == 1) {
                return lists[0];
            }
            PriorityQueue<ListNode> queue = new PriorityQueue((Comparator<ListNode>) (o1, o2) -> {
                return o1.val - o2.val;
            });
            for (ListNode node : lists) {
                queue.add(node);
            }
            ListNode newNode = new ListNode(Integer.MIN_VALUE);
            ListNode curNode = newNode;
            while (!queue.isEmpty()) {
                ListNode minNode = queue.poll();
                curNode.next = minNode;
                curNode = curNode.next;
                if (minNode != null && minNode.next != null) {
                    queue.offer(minNode.next);
                }
            }
            return newNode.next;
        }

        public ListNode mergeKLists1(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            if (lists.length == 1) {
                return lists[0];
            }
            List<ListNode> nodeList = new ArrayList<>(lists.length);
            for (ListNode node : lists) {
                nodeList.add(node);
            }
            ListNode node = mergeKLists(nodeList, 0, lists.length - 1);
            return node;
        }

        public ListNode mergeKLists(List<ListNode> lists, int left, int right) {
            while (left < right) {
                int mid = (right + left) / 2;
                ListNode listNode1 = mergeKLists(lists, left, mid);
                ListNode listNode2 = mergeKLists(lists, mid + 1, right);
                return mergeList(listNode1, listNode2);
            }
            return lists.get(left);
        }

        public ListNode mergeList(ListNode list1, ListNode list2) {
            ListNode newNode = new ListNode(Integer.MIN_VALUE);
            ListNode curNode = newNode;
            while (list1 != null || list2 != null) {
                if (list1 != null && list2 != null && list1.val < list2.val) {
                    curNode.next = list1;
                    list1 = list1.next;
                    curNode = curNode.next;
                }
                if ((list2 != null && list1 != null && list1.val >= list2.val)) {
                    curNode.next = list2;
                    list2 = list2.next;
                    curNode = curNode.next;
                }
                if (list1 == null && list2 != null) {
                    curNode.next = list2;
                    break;
                }
                if (list2 == null && list1 != null) {
                    curNode.next = list1;
                    break;
                }
            }
            return newNode.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}